\chapter{Снова о ящиках}

По материалам лекции от 3 ноября 2011 года.

\subsection{Производящие функции и ящики}

Рассмотрим задачу о распределении неразличимых предметов по различимым ящикам. Для этого рассмотрим еще раз, что происходит с обыкновенными производящими функциями при перемножении:

\[
	\begin{split}
		& f\left(x\right) = a_0 + a_1 x + a_2 x^2 + ... \\
		& g\left(x\right) = b_0 + b_1 x + b_2 x^2 + ... \\
		& h\left(x\right) = f\left(x\right) g\left(x\right) = c_0 + c_1 x + c_2 x^2 \\
		& c_n = \sum_{i=0}^n a_i b_{n-i}
	\end{split}
\]

Пусть теперь у нас есть $n$ предметов и мы желаем разложить их по двум ящикам, тогда, если педметы не различимы, нам важно лишь количество предметов в каждом ящике, т. е. получаются варианты: один ящик пустой, все $n$ предметов попали во второй, в первом ящике 1 предмет, во втором $n-1$, в первом ящике 2 предмета, во втором $n-2$ и тд. Всего количество вариантов в точности $n+1$, и каждый вариант получается только одним способом, т. е. в точности произведение обыкновенных производящих функций при условии $a_i = b_i = 1$.

Экстраполяция на большее число ящиков получается за счет перемножения большего числа производящих функций, теперь сразу к технике, производящая функция для следующей последовательности:
\[
	1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ...
\]
(* когда натренируешься, так прикольно рисовать эти единички=)).

будет следующей:
\[
	f\left(x\right) = \frac{1}{1-x}
\]

таким образом для задачи разложения неразличимых предметов по $k$ различимым ящикам без ограничений на количество предметов в ящике получаем:
\[
	r\left(x\right) = \left(f\left(x\right)\right)^k = \frac{1}{\left(1-x\right)^k} = \sum_{n=0}^{\infty} \binom{n+k-1}{n} x^n
\]
т. е. получили уже известное нам решение - сочетания с повторениями.

Теперь добавим в задачу ограничения, пусть в каждом ящике должен лежать хотябы 1 предмет, тогда рассматриваем последовательность:
\[
	0, 1, 1, 1, 1, 1, 1, ...
\]
производящая функция для нее:
\[
	f\left(x\right) = \frac{x}{1-x}
\]
и решение тогда приобретет вид:
\[
	r\left(x\right) = \left(f\left(x\right)\right)^k = x^k \frac{1}{\left(1-x\right)^k} = x^k \sum_{n=0}^{\infty} \binom{n+k-1}{n} x^n = \sum_{n=0}^{\infty} \binom{n+k-1}{n} x^{n+k}
\]
решение опять же нам известное и раньше.

Теперь перейдем к более сложной задаче, решение которой также было получено ранее, но в очень ограниченной форме. Пусть в каждом ящике не может лежать больше $m$ предметов, тогда рассматриваем следующие последовательности:
\[
	\underbrace{1, 1, 1, ..., 1,}_{m} 0, 0, 0, ...
\]
Производящая функция для такой последовательности есть просто (ну не совсем просто) многочлен:
\[
	f\left(x\right) = 1 + x + x^2 + x^3 + ... + x^m
\]

а результирующая функция:
\[
	r\left(x\right) = \left(f\left(x\right)\right)^k = \left(1 + x + x^2 + x^3 + ... + x^m\right)^k
\]
Получаем уже чисто вычислительную задачу, если число $m$ не очень большое то иногда даже можно руками посчитать, например, пусть в каждом ящике должно быть не более 1 предмета, тогда имеем:
\[
	f\left(x\right) = 1 + x
\]
и результат:
\[
	r\left(x\right) = \left(f\left(x\right)\right)^k = \left(1+x\right)^k = \sum_{n=0}^{k} \binom{k}{n} x^n
\]
получили опять известный нам результат.

\subsection{Композиция производящих функций}

Иногда после того, как мы получили разбиение линейно-упорядоченного множества на блоки (см предыдщуий пункт), над блоками необходимо совершить комбинаторное действие, в этом случае интуитивно поянтно, что должна использоваться композиция производящих функций. Но прежде чем определять такую композицию рассмотрим задачу о марках:

Пусть имеются марки достоинством $4, 6, 10$ требуется наклеить марок на $n$ единиц (порядок наклейки важен, нужно ровно $n$ единиц). Напишем рекуррентное соотношение:
\[
	F\left(n\right) = F\left(n-4\right) + F\left(n-6\right) + F\left(n-10\right)
\]
при начальных условиях:
\[
	\begin{split}
		& F\left(0\right) = 1 \\
		& F\left(n\right) = 0, n < 0
	\end{split}
\]

Теперь воспользуемся известной техникой, построим производящую функцию для решения данной задачи, исходя из того, что последовательность:
\[
	a_0, a_1, a_2, a_3, ...
\]
является решением получаем
\[
	\begin{split}
		& \sum a_{n+10} x^{n+10} = x^4 \sum a_{n+6} x^{n+6} + x^6 \sum a_{n+4} x^{n+4} + x^{10} \sum a_n x^{n} \Leftrightarrow \\
		& \Leftrightarrow f\left(x\right) - 1 - x^4 - x^6 - x^8 = x^4 \left[f\left(x\right) - 1 - x^4\right] + x^6 \left[f\left(x\right) - 1\right] + x^{10} f\left(x\right) \Leftrightarrow \\
		& \Leftrightarrow f\left(x\right) \left[1 - x^4 - x^6 - x^{10}\right] = 1 \Leftrightarrow f\left(x\right) = \frac{1}{1 - \left(x^4 + x^6 + x^{10}\right)}
	\end{split}
\]
не правда ли чудесное совпадение?!?!?!? Но давай всмотримся в полученную функцию, замечаем, что если в производящей функции $\frac{1}{1 - x}$ заменить $x$ на $x^4 + x^6 + x^{10}$ получаем наше выражение, чтобы это значило?

\begin{Def}
Пусть имеются две производящие функции:
\[
	\begin{split}
		& f\left(x\right) = 1 + a_1 x + a_2 x^2 + a_3 x^3 + ... \\
		& g\left(x\right) = 1 + b_1 x + b_2 x^2 + b_3 x^3 + ... \\
	\end{split}
\]
тогда композицией производящих функций называется:
\[
	s\left(x\right) = f\left(g\left(x\right)\right) = 1 + a_1 f\left(x\right) + a_2 \left(f\left(x\right)\right)^2 + a_3 \left(f\left(x\right)\right)^3 + ...
\]
\end{Def}

Теперь посмотрев на определение становится понятно, что в нашем примере в результирующей функции возле $n$-ого коэффициента будет стоять $\left(x^4 + x^6 + x^10\right)^n$ т. е. в точности число способов получить из марок достоинством $4, 6, 10$ сумму в $n$, собственно то, что мы и получили ранее.

Таким образом суть композиции обыкновенных производящих функций в следующем, сначала мы определенным образом разбиваем множество, потом над полученными блоками совершаем некоторое действие. И вот число способов так наворотить как раз и определяется композицией производящих функций.

\subsection{Неразличимые предметы и неразличимые ящики}

Возвращемся к задаче о наклейке марок, но теперь потребум, чтобы порядок наклеки марок был несущественен.

Например, для марок стоимостью $4,6,10$ и суммы $18$ имеем следующе варианты:
\begin{enumerate}
\item $\{6, 6, 6\}$

\item $\{4, 4, 4, 6\}$

\item $\{4, 4, 10\}$
\end{enumerate}

Очевидно, что задача эквивалентна решению уравнения:
\[
	4 \cdot x + 6 \cdot y + 10 \cdot z = 18
\]
причем, $x,y,z \in \mathbb{N}\cup\{0\}$

Введем вспомогательную функцию:
\[
	\Phi \left(4, 6, 10; n\right)
\]
со смыслом: "Решение задачи о наклейке марок стоимостями $4, 6$ или $10$, на общую сумму $n$".

Теперь заюзаем наш любимый метод - <<разделяй и властвуй>>, разобьем все решения на два блока, первый - решения содержащие 10, второй - решения не содержащие 10, тогда, очевидно, справедливо соотношение:
\[
	\Phi\left(4,6,10;n\right) = \Phi\left(4,6,10;n-10\right) + \Phi\left(4,6;n\right)
\]
Ну вообщем такими разбиениями можно раскрывать и дальше, но решать рекуррентные соотношения в таком формате в общем виде не очень то приятная задача, в свое время дядя Эйлер предложил немного другой подход к решению, предысторию пропустим, скажем лишь, что в итоге он получил нужную производящую функцию:
\[
	\begin{split}
		&f\left(x\right) = \frac{1}{1-x^4} \cdot \frac{1}{1-x^6} \cdot \frac{1}{1-x^{10}} = \left(1+x^4+x^8+...\right)\cdot\\
		&\cdot\left(1+x^6+x^{12}+...\right)\cdot\left(1+x^{10}+x^{20}+...\right)
	\end{split}
\]
Может показаться, что решение не очень похоже на решение, но на самом деле это так, и вот наводящая мысль, если мы перемножаем скобки, то проверям слогаемые вида:
\[
	c x^{k_1 \cdot 4 + k_2 \cdot 6 + k_3 \cdot 10}
\]
и тут уже все очевидно (мы выше свели решение исходной задачи к подсчету числа решений целочисленного уравнения).

Проверим для $n=18$, но перед этим заметим, что, хотя, в скобках беконечная сумма, можно опустить все слогаемые со степенями выше 18:
\[
	\begin{split}
		& \left(1+x^4+x^8+x^{12}+x^{16}\right)\cdot\left(1+x^6+x^{12}+x^{18}\right)\cdot\left(1+x^{10}\right) = \\
		& = \left(1+x^4+x^8+x^{12}+x^{16}\right)\cdot\left(1+x^6+x^{10}+x^{12}+x^{16}+x^{18}+x^{22}+x^{28}\right) = \\
		& = 1+x^6+x^{10}+x^{12}+x^{16}+\underline{x^{18}}+...+\\
		& +x^4+x^{10}+x^{16}+...+\\
		& +x^8+x^{14}+\underline{x^{18}}+...+\\
		& +x^{12}+\underline{x^{18}}+...
	\end{split}
\]

Ну в общем не трудно предположить как выглядит решение для произвольных стоимотей марок, поэтому останавливаться на данном вопросе не будем, вместо этого изменим немного условие, пусть у нас имеются ровно по одной марке каждого достоинства.

Решение такой задачи, совершенно очевидно:
\[
	f\left(x\right) = \left(1+x^4\right)\cdot\left(1+x^6\right)\cdot\left(1+x^{10}\right) = 1+x^4+x^6+2\cdot x^{10} + x^{14} + x^{16} + x^{20}
\]

\begin{Def}
Разбиением числа $n$ называется неупорядоченный набор $\{x_i\}$ такой, что $\sum_i x_i = n$ и $n,x_i \in \mathbb{N}$
\end{Def}

Примеры:
\begin{enumerate}
\item $1$

\item $2 = 1+1$

\item $3 = 2+1 = 1+1+1$

\item $4 = 3+1 = 2+2 = 2+1+1 = 1+1+1+1$
\end{enumerate}

Теперь снова о пользе представлений, рассмотрим различные способы представления числа $n$ в виде некоторой суммы:
\begin{enumerate}
\item $n = x_1 + x_2 + ... + x_n$, где $x_i \in \left[0;n\right]$ и $n \ge x_1 \ge x_2 \ge x_3 \ge ... \ge x_n \ge 0$

\item $n = y_1 + 2\cdot y_2 + 3 \cdot y_3 + ... + n \cdot y_n$ и $y_i \ge 0$
\end{enumerate}

Первое представление пока оставим и начнем со второго, производящая функция для числа способов такого представления:
\[
	\begin{split}
		&f\left(x\right) = \left(1+x+x^2+x^3+...\right)\cdot\left(1+x^2+x^4+x^6+...\right)\cdot\\
		&\cdot\left(1+x^3+x^6+x^9+...\right)\cdot ... \cdot\left(1+x^n+x^{2n}+x^{3n}+...\right) = \\
		& = \frac{1}{\left(1-x\right)\left(1-x^2\right)...\left(1-x^n\right)}
	\end{split}
\]

и вправду возвращаясь к задаче о наклейке марок не трудно понять, что между ними есть связь, т. е. разбиение числа на слогаемые эквивалентно наклейке марок на сумму $n$, при условии, что есть марки всех достоинств.

Тут добавим щепотку формализма - производящая функция не должна зависеть от $n$ и на самом деле для таких задач она выглядит следующим образом:
\[
	f\left(x\right) = \prod_{i=1}^{\infty} \frac{1}{1 - x^i}
\]

но на практике, конечно, такая форма бесполезна).

Тепрь пользуясь всем вышеописанным, получим одно забавное следствие.

\paragraph{Задача:} пусть каждое слогаемое может входить в разбиение не больше одного раза (т. е. в данном случае разбиение есть множество).

Производящая функция пишется сходу:
\[
	f\left(x\right)=\left(1+x\right)\cdot\left(1+x^2\right)\cdot\left(1+x^3\right)\cdot...\cdot\left(1+x^n\right)\cdot...
\]

далее пользуемся соотношением:
\[
	\left(1+x^k\right) = \frac{1-x^{2\cdot k}}{1 - x^k}
\]
и заменяем каждую скобку в производящей функции на дробь:
\[
	\begin{split}
		&f\left(x\right) = \frac{1-x^2}{1-x}\cdot\frac{1-x^4}{1-x^2}\cdot\frac{1-x^6}{1-x^3}\cdot...\cdot\frac{1-x^{2\cdot n}}{1 - x^n}... = \\
		& = \frac{1}{\left(1-x\right)\left(1-x^3\right)...\left(1-x^{2\cdot n+1}\right)...}
	\end{split}
\]
итого имеем, что решение нашей задачи совпадает с количеством разбиений числа на нечетные слогаемые.

Но так как у нас день ящиков и того, что можно туд наложить, то снова о ящиках. Рассмотрим две производящие функции:
\[
	\begin{split}
		& f\left(x\right) = 1+x^{j_1}+x^{2j_1}+x^{3j_1}+...\\
		& g\left(x\right) = 1+x^{j_2}+x^{2j_2}+x^{3j_2}+...
	\end{split}
\]
где $0 < j_1 < j_2$

Произведение этих производящих функций:
\[
	h\left(x\right) = f\left(x\right)g\left(x\right) = c_0 + c_1x + c_2x^2 + ...
\]
где $c_n = \sum_{i=0}^n a_ib_{n-i}$, а в свою очередь:
\[
	\begin{split}
		& a_i = \begin{cases}1, \text{ если } i \vdots j_1 \\ 0, \text{ иначе }\end{cases} \\
		& b_i = \begin{cases}1, \text{ если } i \vdots j_2 \\ 0, \text{ иначе }\end{cases}
	\end{split}
\]

Теперь вспоминая смысл произведения обыкновенных производящих функций, как число спсобов разбиения линейно-упорядоченного множества некоторым хитрым способом, подумаем какой же комбинаторный смысл может быть придан $a_i$ и $b_i$.

Придадим им следующий смысл:
\begin{itemize}
\item $a_i$ - количество способов разложить неразличимые предметы по $i/j_1$ ящикам так, чтобы в каждом было по $j_1$ предметов

\item $b_i$ - то же самое, но для $j_2$
\end{itemize}

тогда $c_n$ - количество способов разложить $n$ неразличимых предметов блоками по $j_1$ и $j_2$ по неразличимым ящикам, т. е. количество решений уравнения:
\[
	\begin{split}
		& j_1 \cdot y_1 + j_2 \cdot y_2 = n \\
		& y_1,y_2 \in \mathbb{N}\cup\{0\} \\
		& y_1,y_2 \le n
	\end{split}
\]

И тут мы кричим ура, говорим, что это решение поможет нам решить задачу о раскладке неразличимых предметов по неразличимым ящикам, и все вроде хорошо, и на этом бы можно закончить, но рано радуетесь) - нам в конечно итоге требуется подсчитать количество способов разложения фиксированного количества предметов по фиксированному количеству ящиков, а те кто следил за ходом рассуждения заметили, что в данном решении количество ящиков не фиксированно, но мы получили некоторый полезный иснтрумент, которым мы потом воспользуемся, наверно.

В качестве заключения введем ряд обозначений.

\begin{Def}
$p_k\left(n\right)$ - количество разбиений числа $n$, на $k$ слогаемых

$p\left(n\right) = \sum_{k=1}^n p_k\left(n\right)$ - число всех разбиений числа $n$
\end{Def}

\subsection{Диаграммная техника}

В комбинаторике существует способ не очень формально, зато очень забавно доказывать некоторые комбинаторные соотношения графическим путем - диаграммы Ферре и диаграммы Юнга.

Рассмотрим разложение числа $n=5$ на слогаемые:
\begin{enumerate}
\item $5$

\item $4+1$

\item $3+2$

\item $2+2+1$

\item $2+1+1+1$

\item $1+1+1+1+1$
\end{enumerate}

Каждому такому разбиению сопоставим графическое представление:
\begin{enumerate}
\item $\begin{matrix}
	\bullet & \bullet & \bullet & \bullet & \bullet
	\end{matrix}$

\item $\begin{matrix}
	\bullet & \bullet & \bullet & \bullet \\
	\bullet
	\end{matrix}$

\item $\begin{matrix}
	\bullet & \bullet & \bullet \\
	\bullet & \bullet
	\end{matrix}$

\item $\begin{matrix}
	\bullet & \bullet \\
	\bullet & \bullet \\
	\bullet
	\end{matrix}$

\item $\begin{matrix}
	\bullet & \bullet \\
	\bullet \\
	\bullet \\
	\bullet
	\end{matrix}$

\item $\begin{matrix}
	\bullet \\
	\bullet \\
	\bullet \\
	\bullet \\
	\bullet
	\end{matrix}$
\end{enumerate}

Ну в общем вы уже догадались, но я проговорю, количество строк - количество слогаемых, а количество точек в каждом слогаемом - число, кроме того, количество точек в $\left(i+1\right)$-ом ряду не может быть больше количества точек в $i$-ом.

Диаграммы Юнга выглядят следующим образом:

\begin{enumerate}
\item $\begin{matrix}
	\square & \square & \square & \square & \square
	\end{matrix}$

\item $\begin{matrix}
	\square & \square & \square & \square \\
	\square
	\end{matrix}$

\item $\begin{matrix}
	\square & \square & \square \\
	\square & \square
	\end{matrix}$

\item $\begin{matrix}
	\square & \square \\
	\square & \square \\
	\square
	\end{matrix}$

\item $\begin{matrix}
	\square & \square \\
	\square \\
	\square \\
	\square
	\end{matrix}$

\item $\begin{matrix}
	\square \\
	\square \\
	\square \\
	\square \\
	\square
	\end{matrix}$
\end{enumerate}

Многие щас ничего не поняли, кто-то просто поржал, но дело в том, что в диаграммах Юнга в квадраты можно расставлять числа (веса, если хотите) и придавать этому некоторый смысл, в остальном они не отличаются от диаграмм Ферре.
